home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 06 - 1990 / 06.08 Aug 90 / B Trees Source / Binary Tree / Binary.c next >
Encoding:
C/C++ Source or Header  |  1989-12-25  |  5.8 KB  |  318 lines  |  [TEXT/nX^n]
  1. //////////////////////////////////////////////////////////////////
  2. //    
  3. //        Binary.c
  4. //        --------
  5. //        Binary tree search and insertion
  6. //    
  7. //////////////////////////////////////////////////////////////////
  8.     
  9. #pragma load "managers"
  10.     
  11. //////////////////////////////////////////////////////////////////
  12. //    
  13. //        Constants and Macros
  14. //    
  15. //////////////////////////////////////////////////////////////////
  16.     
  17. #define nil                    0
  18.     
  19. //////////////////////////////////////////////////////////////////
  20. //    
  21. //        Types
  22. //    
  23. //////////////////////////////////////////////////////////////////
  24.     
  25. typedef enum {false, true} logical;
  26.  
  27. typedef struct node
  28.     {
  29.     char                *key;
  30.     struct node        *left;
  31.     struct node        *right;
  32.     char                *data;
  33.     } node;
  34.     
  35. //////////////////////////////////////////////////////////////////
  36. //    
  37. //        Globals
  38. //    
  39. //////////////////////////////////////////////////////////////////
  40.     
  41. //////////////////////////////////////////////////////////////////
  42. //    
  43. //        Prototypes
  44. //    
  45. //////////////////////////////////////////////////////////////////
  46.     
  47.     void initmac();
  48.     node *createnode(char *thekey, char *thedata);
  49.     node *insert(node *thetable, char *thekey, char *thedata);
  50.     node *lookup(node *thetable, char *thekey);
  51.     void dump(node *thetable);
  52.     void destroy(node *thetable);
  53.     
  54. //////////////////////////////////////////////////////////////////
  55. //
  56. //        main
  57. //        ----
  58. //        Test shell for lookup table package
  59. //
  60. //////////////////////////////////////////////////////////////////
  61.     
  62. main()
  63.     {
  64.     
  65.     node                *thetable;
  66.     char                thestring[256];
  67.     char                command;
  68.     char                thekey[256];
  69.     char                thedata[256];
  70.     node                *thenode;
  71.     
  72.     initmac();
  73.     
  74.     thetable = createnode("", "");
  75.     if (thetable == nil)
  76.         {
  77.         printf("\tUnable to create table\n");
  78.         exit(2);
  79.         }
  80.     
  81.     printf("? ");
  82.     while (true)
  83.         {
  84.         
  85.         gets(thestring);
  86.         sscanf(&thestring[2], "%c %s %[^\n]", &command, thekey, thedata);
  87.         
  88.         switch (command)
  89.             {
  90.             
  91.             case 'A':
  92.             case 'a':
  93.                 if (insert(thetable, thekey, thedata) == nil)
  94.                     printf("\tKey already exists in table\n");
  95.                 break;
  96.             
  97.             case 'D':
  98.             case 'd':
  99.                 dump(thetable->right);
  100.                 break;
  101.             
  102.             case 'F':
  103.             case 'f':
  104.                 thenode = lookup(thetable, thekey);
  105.                 if (thenode == nil)
  106.                     {
  107.                     printf("\tKey not found in table\n");
  108.                     break;
  109.                     }
  110.                 printf("\tData is “%s”\n", thenode->data);
  111.                 break;
  112.             
  113.             case 'Q':
  114.             case 'q':
  115.                 destroy(thetable);
  116.                 exit(0);
  117.             
  118.             }
  119.         
  120.         printf("? ");
  121.         
  122.         }
  123.     
  124.     }
  125.     
  126. //////////////////////////////////////////////////////////////////
  127. //
  128. //        initmac
  129. //        -------
  130. //        initialize any necessary managers and whatnot.
  131. //
  132. //////////////////////////////////////////////////////////////////
  133.     
  134. void initmac()
  135.     {
  136.     
  137.     InitGraf((Ptr)&qd.thePort);
  138.     SetFScaleDisable(true);
  139.     
  140.     InitCursorCtl(nil);
  141.     
  142.     }
  143.     
  144. //////////////////////////////////////////////////////////////////
  145. //
  146. //        createnode
  147. //        ----------
  148. //        create and initialize a new node
  149. //
  150. //////////////////////////////////////////////////////////////////
  151.     
  152. node *createnode(char *thekey, char *thedata)
  153.     {
  154.     
  155.     node                *thenode;
  156.     int                thelength;
  157.     
  158.     thenode = (node *)NewPtr(sizeof(node));
  159.     if (thenode == nil)
  160.         return(nil);
  161.     
  162.     thelength = 1 + strlen(thekey);
  163.     thenode->key = (char *)NewPtr(thelength);
  164.     if (thenode->key == nil)
  165.         {
  166.         DisposPtr((Ptr)thenode);
  167.         return(nil);
  168.         }
  169.     BlockMove((Ptr)thekey, (Ptr)thenode->key, thelength);
  170.     
  171.     thenode->left = nil;
  172.     thenode->right = nil;
  173.     
  174.     thelength = 1 + strlen(thedata);
  175.     thenode->data = (char *)NewPtr(thelength);
  176.     if (thenode->data == nil)
  177.         {
  178.         DisposPtr((Ptr)thenode->key);
  179.         DisposPtr((Ptr)thenode);
  180.         return(nil);
  181.         }
  182.     BlockMove((Ptr)thedata, (Ptr)thenode->data, thelength);
  183.     
  184.     return(thenode);
  185.     
  186.     }
  187.     
  188. //////////////////////////////////////////////////////////////////
  189. //
  190. //        insert
  191. //        ------
  192. //        Insert a new key into the table
  193. //
  194. //////////////////////////////////////////////////////////////////
  195.     
  196. node *insert(node *thetable, char *thekey, char *thedata)
  197.     {
  198.     
  199.     node                *thenode;
  200.     int                compare;
  201.     node                *thechild;
  202.     
  203.     thenode = thetable;
  204.     
  205.     while (compare = strcmp(thekey, thenode->key))
  206.         {
  207.         
  208.         if (compare < 0)
  209.             {
  210.             
  211.             thechild = thenode->left;
  212.             if (thechild == nil)
  213.                 {
  214.                 thenode->left = createnode(thekey, thedata);
  215.                 return(thenode->left);
  216.                 }
  217.             
  218.             }
  219.         else
  220.             {
  221.             
  222.             thechild = thenode->right;
  223.             if (thechild == nil)
  224.                 {
  225.                 thenode->right = createnode(thekey, thedata);
  226.                 return(thenode->right);
  227.                 }
  228.             
  229.             }
  230.         
  231.         thenode = thechild;
  232.         
  233.         }
  234.     
  235.     return(nil);
  236.     
  237.     }
  238.     
  239. //////////////////////////////////////////////////////////////////
  240. //
  241. //        lookup
  242. //        ------
  243. //        Find a key in the table
  244. //
  245. //////////////////////////////////////////////////////////////////
  246.     
  247. node *lookup(node *thetable, char *thekey)
  248.     {
  249.     
  250.     node                *thenode;
  251.     int                compare;
  252.     
  253.     thenode = thetable;
  254.     
  255.     while (compare = strcmp(thekey, thenode->key))
  256.         {
  257.         if (compare < 0)
  258.             thenode = thenode->left;
  259.         else
  260.             thenode = thenode->right;
  261.         if (thenode == nil)
  262.             return(nil);
  263.         }
  264.     
  265.     return(thenode);
  266.     
  267.     }
  268.     
  269. //////////////////////////////////////////////////////////////////
  270. //
  271. //        dump
  272. //        ----
  273. //        Display the table, node by node
  274. //
  275. //////////////////////////////////////////////////////////////////
  276.     
  277. void dump(node *thetable)
  278.     {
  279.     
  280.     if (thetable == nil)
  281.         return;
  282.     
  283.     dump(thetable->left);
  284.     
  285.     printf("%10s - %10s - %10s\n",
  286.                     thetable->key,
  287.                     thetable->left ? thetable->left->key : "nil",
  288.                     thetable->right ? thetable->right->key : "nil");
  289.     
  290.     dump(thetable->right);
  291.     
  292.     }
  293.     
  294. //////////////////////////////////////////////////////////////////
  295. //
  296. //        destroy
  297. //        -------
  298. //        Dispose of the table
  299. //
  300. //////////////////////////////////////////////////////////////////
  301.     
  302. void destroy(node *thetable)
  303.     {
  304.     
  305.     if (thetable == nil)
  306.         return;
  307.     
  308.     destroy(thetable->left);
  309.     destroy(thetable->right);
  310.     
  311.     DisposPtr((Ptr)thetable->key);
  312.     DisposPtr((Ptr)thetable->data);
  313.     DisposPtr((Ptr)thetable);
  314.     
  315.     }
  316.     
  317. //////////////////////////////////////////////////////////////////
  318.